package leetcode.editor.week.week313;

// 6194. 最小 XOR
// https://leetcode.cn/problems/minimize-xor/
public class Solution6194 {
    // https://leetcode.cn/problems/minimize-xor/solution/by-xie-zhi-xing-c-b87u/
    public int minimizeXor(int num1, int num2) {
        int count = cal(num2);
        char[] arr = Integer.toBinaryString(num1).toCharArray();
        int n = arr.length;

        // 优先填充前面的1，后面的都为0
        for (int i = 0; i < n; i++) {
            if (count > 0) {
                if (arr[i] == '1') {
                    count--;
                    continue;
                }
            }

            // 后面的填充为0
            if (arr[i] == '1') {
                arr[i] = '0';
            }
        }

        // 如果多了，从后向前来遍历
        for (int i = n - 1; i >= 0; i--) {
            if (count > 0) {
                if (arr[i] == '0') {
                    arr[i] = '1';
                    count--;
                }
            } else break;

        }

        // 这时可能个数还不够，先把nums1长度的值算出来，再补不够的
        int res = 0;
        int i, j;
        for (i = 0, j = n - 1; j >= 0; i++, j--) {
            if (arr[j] == '1') {
                res += Math.pow(2, i);
            }
        }

        // 补上不够的
        while (count > 0) {
            res += Math.pow(2, i++);
            count--;
        }

        return res;
    }

    // 计算二进制1的个数
    int cal(int x) {
        int count = 0;
        while (x != 0) {
            if ((x & 1) == 1) count++;
            x >>= 1;
        }

        return count;
    }
}
